package com.zyy.study.sort;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] array = {2, 3, 5, 2, 1, 5, 7, 83, 2, 5987, 4, 0, 12, 54};
        sort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }


    public static void sort(int[] array, int start, int end) {
        if (start < end) {
            int index = getIndex(array, start, end);
            sort(array, start, index - 1);
            sort(array, index + 1, end);
        }
    }

    public static int getIndex(int[] array, int start, int end) {
        int i = start;
        int j = end;
        int p = array[start];
        while (i < j) {
            while (i < j && array[j] >= p) {
                j--;
            }
            while (i < j && array[i] <= p) {
                i++;
            }
            swap(array, i, j);
        }
        swap(array, start, i);
        return i;
    }

    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}
